import java.util.*;
 
 /** 
 * Specializza la classe AlgorithmBase implementando la logica di calcolo dei
 * percorsi minimi secondo l'algoritmo di BellmanFord. 
 * L'algoritmo di BellmanFord funziona correttamente anche in presenza di cicli
 * negativi poiché è in grado di rilevarne la presenza e segnalarla all'utente
 * tramite il log.
 *    
 * @author Massimiliano Ferretti matricola 79769 
 */

 public class BellmanFord 
  extends AlgorithmBase
  {
    private List<Node> set;
  
    public String getName()
    {
      return "Bellman-Ford";
    }

    private boolean relax(Arc arc)
    {
      Node source = arc.getSource();
      Node target = arc.getTarget();
      boolean result = false;
      
      if(source.isDistanceInfinite())
        return false;
        
	    // Relax
      if(source.getDistance() + arc.getWeight() < target.getDistance())
  	  {
        int newDistance = source.getDistance() + arc.getWeight();                                                                                
        arc.getTarget().setDistance(newDistance);
        arc.getTarget().setPrevious(source);
        result = true;
  	  }   
      
      return result;
    }
    
    public void execute()
    {
      // System.out.println("Inizio " + getName() + "\n");
      log("Inizio " + getName());
    
      for(int iterazione=0; iterazione < nodes.length; iterazione++)
      {
        for(Arc arc : arcs)
          if(relax(arc))
          {
            Node source = arc.getSource();
            Node target = arc.getTarget();
          
            // System.out.println("(" + source.getIndex() + "->" + target.getIndex() + ") Nodo: " + target.getIndex() + " relax da: " + target.getDistance() + " a: " + (source.getDistance() + arc.getWeight()));
            log("(" + source.getIndex() + "->" + target.getIndex() + ") Nodo: " + target.getIndex() + " relax da: " + target.getDistance() + " a: " + (source.getDistance() + arc.getWeight()));
          } else
          {
            Node source = arc.getSource();
            Node target = arc.getTarget();

            // Non c'e bisogno di Relax
            // System.out.println("Nodo: " + target.getIndex() + " rimane a: " + target.getDistance() + ", non ha bisogno di relax");
            log("Nodo: " + target.getIndex() + " rimane a: " + target.getDistance() + ", non ha bisogno di relax");
          }
      }
      
      // Esegue un'ultima operazione di relax per vedere se esistono 
      // cicli negativi
      for(Arc arc : arcs)
        if(relax(arc))
        {
          // System.out.println("Attenzione! Presenza di cicli negativi!");
          log("Attenzione! Presenza di cicli negativi!");
          break;
        }
    }
}
